package DifficultPractice;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

import org.junit.Test;

public class Demo773 {
//	
//	773. 滑动谜题
//	在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
//
//	一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
//
//	最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
//
//	给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
	
	public int slidingPuzzle(int[][] board) {
		
		String target = "123450";
		StringBuffer sb = new StringBuffer();
		
		for(int i=0; i<2; i++) {
			for(int j=0; j<3; j++) {
				sb.append( (char)(board[i][j] + '0' ));
			}
		}
		String init = sb.toString();
		
		int[][] neighbor = {
				{1, 3},
				{0, 2, 4},
				{1, 5},
				{0, 4},
				{1, 3, 5},
				{2, 4}
		};
		
		Queue<String> queue = new LinkedList<>();
		Set<String> memo = new HashSet<>();
		int step = 0;
		
		queue.offer(init);
		memo.add(init);
		
		while(!queue.isEmpty()) {
			
			int nextSize = queue.size();
			for(int i=0; i<nextSize; i++) {
				
				String choice = queue.poll();
				
				if(choice.equals(target)) {
					return step;
				}
				
				int zerondex = findIndex(choice);
				//if(zerondex == -1)	return -1;
				
				for(int n : neighbor[zerondex]) {
					String nextStep = swap(choice, n, zerondex);
					
					if(!memo.contains(nextStep)){
						queue.offer(nextStep);
						memo.add(nextStep);
					}
				}
			}
			step++;
		}
		
		return -1;
		
    }
	
	private String swap(String choice, int n, int zerondex) {
		
		char[] arr = choice.toCharArray();
		char temp = arr[n];
		arr[n] = arr[zerondex];
		arr[zerondex] = temp;
		return new String(arr);
	}

	private int findIndex(String choice) {
	
		for(int i=0; i<choice.length(); i++) {
			if(choice.charAt(i) == '0') {
				return i;
			}
		}
		
		return -1;
	}

	@Test
	public void myTest773() {
		System.out.println(findIndex("123450"));
		System.out.println(swap("123450", 2, 5));
	}

	
}
